原文題目
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

題目摘要

1. 給定一個整數數組 nums 和一個整數 k，回傳總共多少個子陣列的元素和等於 k。

• 子陣列是陣列中連續的非空元素序列

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

解題思路

1. 使用前綴和與HashMap：
   • 定義「前綴和」為從陣列起始位置到當前位置的累積和。對於每一個位置 i，計算 sum，即 nums 陣列從起始到位置 i 的和。
   • 使用雜湊表 map 來記錄每個前綴和出現的次數，方便快速檢查是否存在符合條件的子陣列。
   • 初始化雜湊表 map，並將前綴和為 0 的計數設為 1。這樣可以處理從陣列開頭開始的子陣列，因為前綴和為 0 表示當前子陣列直接和等於 k。
2. 遍歷陣列並更新前綴和：
   • 遍歷整個陣列 nums，每次更新當前的前綴和 sum，即將當前元素加到累積和上。
   • 檢查 sum - k 是否存在於雜湊表 map 中，如果存在，則說明從某個之前的位置到當前位置的子陣列總和等於 k，將雜湊表中該值對應的計數加到 count 中。
   • 更新雜湊表 map：將當前前綴和 sum 的計數更新，如果 sum 已存在於雜湊表中，則增加其計數；如果不存在，則將其計數設為 1。
3. 回傳結果：
   當遍歷完成後，最後回傳 count 中儲存的即為所有符合條件的子陣列總數。

程式碼

class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>(); //設立一個HashMap來存儲前綴和以及它們出現的次數
        map.put(0, 1); //初始前綴和為0且出現過一次，這樣能夠處理從陣列開頭開始的子陣列
        
        int sum = 0; //當前的前綴和
        int count = 0; //符合條件的子陣列數量

        //遍歷整個陣列
        for (int num : nums) {
            sum += num; //更新當前的前綴和，將當前元素加入總和
            
            //檢查當前的前綴和減去目標值k是否存在於HashMap中
            //如果存在則說明從某個之前的位置到當前位置的子陣列總和等於k
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k); //將該前綴和出現的次數加到結果中
            }
            
            //獲取當前前綴和在Hashmap中出現的次數且默認為 0
            int currentCount = map.getOrDefault(sum, 0);
            
            //將前綴和出現次數加1
            map.put(sum, currentCount + 1);
        }
        
        return count; //回傳符合條件的子陣列數量
    }
}

結論
這題我使用前綴和與 HashMap 來解決問題，前綴和幫助我們快速計算從數組開頭到當前位置的累積和，而 HashMap 記錄前綴和出現的次數，使我們能夠在一次遍歷中找到所有符合條件的子陣列。具體過程是遍歷陣列時，持續更新當前的前綴和，並檢查是否有符合 sum - k 的前綴和存在於 HashMap 中，如果有，則表明存在和為 k 的子陣列。如此一來，不僅有效提升了效率，還避免了暴力解法的多餘計算。